package org.example.sword2offer.primary;
/**
 * https://blog.csdn.net/sc179/article/details/109864895
 */

import java.util.*;

public class Q27_Permutation_H {

    public  String[] permutation(String s) { //fixme 字符串全排列
        List<String> res = new LinkedList<>();//fixme，String
        char[] c = s.toCharArray();
        dfs(c,res,0);
        // List方法：<T> T[] toArray(T[] a)以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; 返回的数组的运行时类型是指定数组的运行时类型。
        return res.toArray(new String[]{}); //fixme list转数组,new String[]{} 数组
    }
    void dfs(char[] c,List<String> res,int x) {
        if(x == c.length - 1) {
            res.add(String.valueOf(c)); // 添加排列方案
            return;
        }
        Set<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) { //fixme i==x
            if(set.contains(c[i])) continue; // 重复，因此剪枝
            set.add(c[i]);
            swap(c,i, x); // 交换，将 c[i] 固定在第 x 位
            dfs(c,res,x + 1); // fixme x+1 开启固定第 x + 1 位字符
            swap(c,i, x); // 恢复交换
        }
    }
    void swap(char[] c,int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
    public static void main(String[] args) {
        Q27_Permutation_H permutation=new Q27_Permutation_H();
        String[] res= permutation.permutation("abc");
        System.out.println(Arrays.toString(res));
    }
}
